package com.xiaoyu.bitOperation;

import java.util.Arrays;

/**
 * @program: DS_and_A
 * @description: 比特位计数
 *
 * 给定一个非负整数num。对于0 ≤ i ≤ num 范围中的每个数字i，计算其二进制数中的 1 的数目并将它们作为数组返回。
 *
 * 示例2:
 * 输入: 5
 * 输出: [0,1,1,2,1,2]
 * 进阶:
 *
 * 给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗？
 * 要求算法的空间复杂度为O(n)。
 *
 * @author: YuWenYi
 * @create: 2021-05-29 11:35
 **/
public class CountBits_338 {

    public static int[] countBits(int n) {
        int[] res = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            String binaryString = Integer.toBinaryString(i);
            int num = i;
            int count = 0;
            for (int j = 0; j < binaryString.length(); j++) {
                if ((num & 1) == 1){
                    count++;
                }
                num = num >> 1;
                if (num == 0) res[i] = count;
            }
        }
        return res;
    }

    //解法二:使用DP
    public static int[] countBits1(int n) {
        int[] res = new int[n + 1];
        int range = 0;
        res[0] = 0;
        int j = 0;
        //将数字分段[1],[2,3],[4,7],[8,15]等,每一段的数字是前面所有段对应位置的数字然后再+1
        //例如[4,7] --> dp[4] = dp[0] + 1  dp[5] = dp[1] + 1,以此类推!
        //加入下一段后就需要重新置0,例如dp[8] = dp[0] + 1,依次类推!
        for (int i = 1; i <= n; i++) {
            String bs = Integer.toBinaryString(i);
            if (bs.length() > range){  //当出现新的一段的时候,重新设j=0
                j = 0;
            }
            res[i] = res[j] + 1;
            j++;
            range = bs.length();
        }
        return res;
    }

    //官方题解--> 我的解法二的改编版! --> 个人没有想到使用(i & (i-1)) == 0!!,太妙了
    //dp公式:bits[i]=bits[j]+1。  j为highBit
    //如果i&(i-1)=0，则令highBit = i，更新当前的最高有效位。
    public static int[] countBits3(int n) {
        int[] res = new int[n + 1];
        int highBit = 0;
        for (int i = 1; i <= n; i++) {
            if ((i & (i-1)) == 0){
                highBit = i;
            }
            res[i] = res[i - highBit] + 1;
        }
        return res;
    }


    //使用官方API
    public static int[] countBits2(int n) {
        int[] res = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            int count = Integer.bitCount(i);
            res[i] = count;
        }
        return res;
    }

    public static void main(String[] args) {
        int[] ints = countBits3(5);
        System.out.println(Arrays.toString(ints));
    }
}
